package 题目集.hash.字符串哈希;

import org.junit.Test;

import java.util.*;

/**
 * DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。
 * 例如，"ACGAATTCCG" 是一个 DNA序列 。
 * 在研究 DNA 时，识别 DNA 中的重复序列非常有用。
 * 给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
 * https://leetcode.cn/problems/repeated-dna-sequences/description/
 */
public class 重复的DNA序列 {
    static int p = 131;
    static long[] base;
    static long[] hash;
    static int n;

    public List<String> findRepeatedDnaSequences(String s) {
        n = s.length();
        base = new long[n + 1];
        hash = new long[n + 1];
        base[0] = 1;
        for (int i = 1; i <= n; i++) {
            base[i] = base[i - 1] * p;
        }
        for (int i = 1; i <= n; i++) {
            hash[i] = hash[i - 1] * p + s.charAt(i - 1);
        }
        Map<Long, int[]> map = new HashMap<>();    //存储两个端点
        Set<String> res = new HashSet<>();
        for (int r = 10; r <= n; r++) {
            int l = r - 10;
            long h = hash(l + 1, r);    //hash是1开始，且左闭右闭
            int[] ints = map.get(h);
            if (ints != null) {
                res.add(s.substring(ints[0], ints[1]));
            } else {
                map.put(h, new int[]{l, r});
            }
        }
        return new ArrayList<>(res);
    }

    public long hash(int l, int r) {
        return hash[r] - hash[l - 1] * base[r - l + 1];
    }

    @Test
    public void test() {
        String s = "AAAAAAAAAAAAA";
        List<String> res = findRepeatedDnaSequences(s);
        res.forEach(System.out::println);
    }
}
